package com.jiang.daily.Q2218;

import java.util.Arrays;
import java.util.List;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/21 21:56
 */
class Solution {
    // 0-1背包问题
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int[] dp = new int[k + 1]; // dp[i]表示i次操作后硬币面值的最大和
        // 状态转移方程：
        // dp[i] = dp[i - t] + 某个栈取出了t个硬币的最大价值(1 <= t <= i)
        Arrays.fill(dp, 0);
        for (List<Integer> pile: piles) { // 每个栈在第1 ~ k次操作的最大价值
            for (int i = k; i > 0; i--) { // 表示当前栈在第i次操作的最大价值
                int value = 0;
                for (int t = 1; t <= pile.size(); t++) { // 表示当前栈取出了t个硬币
                    if (i < t) { // 如果当前操作数小于了当前栈取出硬币数，则退出当前循环
                        break;
                    }
                    value += pile.get(t - 1);
                    dp[i] = Math.max(dp[i], dp[i - t] + value);
                }
            }
        }
        return dp[k];
    }
}
